package cn.com.ctcloud.algorithm.distance;

/**
 * 编辑距离 (Levenshtein Distance算法)
 * <p>
 * 给定两个字符串A和B，求字符串A至少经过多少步字符操作变成字符串B
 * <p>
 * 可用于筛选相似试题：对题库中的试题进行重复性检测,可以保持题库的高质量,并能降低专家的工作强度,也是进行题库资源整合的前提条件
 * <p>
 * 可用于筛选重复文章：对某栏目下的文章进行标题重复性筛选，避免录入重复或相似文章
 */
public class MinimumEditDistance {

	public static void main(String[] args) {
		MinimumEditDistance med = new MinimumEditDistance();
		System.out.println(med.similarDegree("execution", "intention")); // 8

		System.out.println(med.similarDegree("今麦郎", "今麦良")); // 2

		System.out.println(med.similarDegree("康师傅", "唐师傅")); // 2

		System.out.println(med.similarDegree("康师傅", "唐师傅")); // 2

		System.out.println(med.similarDegree("对传播虚假气象预报行为的处罚", "对传播虚假天气预报的处罚")); // 4
	}

	public int similarDegree(String source, String target) {
		if (source == null || target == null)
			throw new IllegalArgumentException("illegal input String");

		int sourceLen = source.length();
		int targetLen = target.length();

		int[][] dp = new int[sourceLen + 1][targetLen + 1];
		//init
		dp[0][0] = 0;
		for (int i = 1; i <= sourceLen; i++)
			dp[i][0] = i;
		for (int i = 1; i <= targetLen; i++)
			dp[0][i] = i;

		for (int i = 1; i <= sourceLen; i++) {
			for (int j = 1; j <= targetLen; j++) {
				if (source.charAt(i - 1) == target.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1];
				} else {
					int insert = dp[i][j - 1] + 1; //source[0,i] to target[0,j-1] then insert target[j]
					int delete = dp[i - 1][j] + 1; //source[0,i-1] to target[0,j] then delete source[i]
					int substitute = dp[i - 1][j - 1] + 2; //source[0,i-1] to target[0,j-1] then substitute(source[i] by target[j])

					int min = min(insert, delete, substitute);
					dp[i][j] = min;
				}
			}
		}
		return dp[sourceLen][targetLen];
	}

	private int min(int insert, int delete, int substitute) {
		int tmp = insert < delete ? insert : delete;
		int min = tmp < substitute ? tmp : substitute;
		return min;
	}
}
